/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/5/12
 * \* Time: 18:03
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 把数组排成最小的数 {
    public String minNumber(int[] nums) {
        String[] strs=new String[nums.length];
        for(int i=0;i< nums.length;i++){
            strs[i]=String.valueOf(nums[i]);
        }
        quickSort(strs,0, strs.length-1);
        StringBuilder res = new StringBuilder();
        for(String s : strs) {
            res.append(s);
        }
        return res.toString();
    }

    /**
     * 自定义字按典序比较大小
     * @param s1
     * @param s2
     * @return
     */
    int compare(String s1,String s2){
//        int n1=s1.length();
//        int n=n1+s2.length();
//        int p1=0,p2=n1;
//        for(int i=0;i<n;i++){
//            char x=p1<n1? s1.charAt(i):s2.charAt(p1-n1);
//            char y = p2 < n ? s2.charAt(p2-n1) : s1.charAt(p2%n);
//            if(x!=y){
//                if(x-y-'0'>0){
//                    return 1;
//                }else{
//                    return -1;
//                }
//            }
//            p1++;
//            p2++;
//        }
//        return 0;
        if((s1+s2).compareTo(s2+s1)>0){
            return 1;
        }else if((s1+s2).compareTo(s2+s1)<0){
            return -1;
        }
        return 0;
    }

    /**
     * 快排
     * @param strs
     * @param left
     * @param right
     */
    public void quickSort(String[] strs,int left,int right){
        if(left<right){
            int pivot=Partion(strs, left, right);
            quickSort(strs,left,pivot-1);
            quickSort(strs,pivot+1,right);
        }
    }

    public int Partion(String[] strs,int left,int right){
        String pivot=strs[left];
        while (left<right){
            while (left<right&&(pivot+strs[right]).compareTo(strs[right]+pivot)<0){right--;}
            strs[left]=strs[right];
            while (left<right&&(pivot+strs[left]).compareTo(strs[left]+pivot)>0){left++;}
            strs[right]=strs[left];
        }
        strs[left]=pivot;
        return left;
    }
}